package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/2/19 9:26
 */
public class No64_最小路径和 {
    public static void main(String[] args) {
        Solution64 solution64 = new Solution64();
        int[][] grid = new int[][]{
                {1, 3, 7},
                {2, 99, 1},
                {6, 38, 9}
        };
        int minNum = solution64.minPathSum(grid);
        System.out.println(minNum);
    }
    
}

class Solution64 {
    public int minPathSum(int[][] grid) {
        // 一维数组
        int x = grid.length;
        int y = grid[0].length;
        //定义
        int[] dp = new int[y];

        for (int i = 0; i < y; i++) {
            //初始化动态规划数组
            if (i == 0) {
                dp[i] = grid[0][0];
            } else {
                dp[i] = dp[i - 1] + grid[0][i];
            } 
        }
        
        //定义迭代次数
        int diedai = x;
        //索引从0开始
        for (int i = 1; i < x; i++) {
            //迭代的时候,这一行的数组每个元素都要迭代
            for (int j = 0; j < y; j++) {
                if (j - 1 >= 0) {
                    dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
                } else {
                    dp[j] = dp[j] + grid[i][j];
                } 
            }
        }
        return dp[y - 1];
    }
}



    //public int minPathSum(int[][] grid) {
    //    //动态规划:dp[x][y]为0,0->x,y的最小路径和
    //    int x = grid.length;
    //    int y = grid[0].length;
    //    //定义
    //    int[][] dp = new int[x][y];
    //    
    //    //开始计算
    //    for (int i = 0; i < x; i++) {
    //        for (int j = 0; j < y; j++) {
    //            //如果x,y皆超出,即0,0这个位置,这时候:
    //            if (i == 0 && j == 0) {
    //                dp[i][j] = grid[0][0];
    //            } else {
    //                if (i - 1 >= 0 && j - 1 >= 0) {
    //                    //全部没有超出
    //                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    //                } else {
    //                    //如果y超出
    //                    if (j - 1 < 0) {
    //                        dp[i][j] = dp[i - 1][j] + grid[i][j];
    //                    } else {
    //                        //x超出
    //                        dp[i][j] = dp[i][j - 1] + grid[i][j];
    //                    } 
    //                } 
    //            } 
    //        }
    //    }
    //    //右下角
    //    return dp[x - 1][y - 1];
    //}



    ////全局变量
    //int minRes = Integer.MAX_VALUE;
    //public int minPathSum(int[][] grid) {
    //    //暴力法
    //    minPathSum(grid, 0, 0, 0);
    //    return minRes;
    //}
    //
    //public void minPathSum(int[][] grid, int x, int y, int sum) {
    //    
    //    //注意超出
    //    if (x >= grid.length) {
    //        return;
    //    }
    //    if (y >= grid[0].length) {
    //        return;
    //    }
    //    
    //    //没有超出,当前值加入
    //    sum += grid[x][y];
    //
    //    //说明当前x,y在右下角
    //    if (x == grid.length - 1 && y == grid[0].length - 1) {
    //        //可以赋值最小变量
    //        minRes = Math.min(minRes, sum);
    //    }
    //    
    //    //下一轮
    //    minPathSum(grid, x + 1, y, sum);
    //    minPathSum(grid, x, y + 1, sum);
    //    //注意,加完回溯,以便下次计算
    //    sum -= grid[x][y];
    //}
